// Package _4_二叉树的层序遍历 main
// @Title _4_二叉树的层序遍历
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 18:55
// @Create  2022-01-14 18:55
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := TreeNode{
		1,
		&TreeNode{
			2,
			&TreeNode{
				4,
				nil,
				nil,
			},
			&TreeNode{
				5,
				nil,
				nil,
			},
		},
		&TreeNode{
			3,
			&TreeNode{
				6,
				nil,
				nil,
			},
			&TreeNode{
				7,
				nil,
				nil,
			},
		},
	}
	fmt.Println(levelRange(&root))
	fmt.Println(levelRange2(&root))
}

func levelRange(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var ans []int
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		// 出队
		temp := queue[0]
		queue = queue[1:]
		ans = append(ans, temp.Val)
		if temp.Left != nil {
			queue = append(queue, temp.Left)
		}
		if temp.Right != nil {
			queue = append(queue, temp.Right)
		}
	}

	return ans
}

func levelRange2(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var ans [][]int
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		var tempArr []int
		for i := 0; i < size; i++ {
			temp := queue[0]
			queue = queue[1:]
			tempArr = append(tempArr, temp.Val)
			if temp.Left != nil {
				queue = append(queue, temp.Left)
			}
			if temp.Right != nil {
				queue = append(queue, temp.Right)
			}
		}
		ans = append(ans, tempArr)
	}
	return ans
}
